Pattern matching in Lempel-Ziv compressed strings: fast, simple, and deterministic

摘要

Countless variants of the Lempel-Ziv compression are widely used in manyreal-life applications. This paper is concerned with a natural modification ofthe classical pattern matching problem inspired by the popularity of suchcompression methods: given an uncompressed pattern s[1..m] and a Lempel-Zivrepresentation of a string t[1..N], does s occur in t? Farach and Thorup gave arandomized O(nlog^2(N/n)+m) time solution for this problem, where n is the sizeof the compressed representation of t. We improve their result by developing afaster and fully deterministic O(nlog(N/n)+m) time algorithm with the samespace complexity. Note that for highly compressible texts, log(N/n) might be oforder n, so for such inputs the improvement is very significant. A (tiny)fragment of our method can be used to give an asymptotically optimal solutionfor the substring hashing problem considered by Farach and Muthukrishnan.